package leetcode.tree.binary.sort;

import leetcode.tree.binary.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 98. 验证二叉搜索树
 *
 * 检查该树是否是二叉排序树
 *
 */
public class IsValidBST {

    /**
     * 全局变量
     * 保存递归实现中序遍历的前一个元素的值
     */
    private long pre = Long.MIN_VALUE;

    public static void main(String[] args) {
        IsValidBST solution = new IsValidBST();
        TreeNode tree = solution.createTree();
        boolean res = solution.isValidBST(tree);
        System.out.println(res);
    }

    /**
     * 创建树
     *
     * @return
     */
    public TreeNode createTree() {
        TreeNode root = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(6);
        root.left = node1;
        root.right = node2;
        node2.left = node3;
        node2.right = node4;
        return root;
    }

    /**
     * 中序遍历 栈实现的
     *
     * 中序遍历二叉排序树得到的序列一定是升序序列
     *
     * @param root  树对象
     * @return
     */
    public boolean isValidBST1(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        double inorder = -Double.MAX_VALUE;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            // 从栈中弹出节点, 指针指向弹出的节点, 这边就是向上层节点进行了回溯
            root = stack.pop();

            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root.val <= inorder) {
                return false;
            }
            inorder = root.val;
            root = root.right;
        }
        return true;
    }


    /**
     * 中序遍历 递归实现
     *
     * @param root 树对象
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        // 叶子节点的左节点或者右节点为null 返回true
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isValidBST(root.right);
    }

}
